package C036;

import com.sun.source.tree.Tree;

import java.util.HashMap;

/**
 * ClassName: C08
 * Package: C036
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/1/21 20:38
 * @Version 1.0
 * @Since 1.0
 */
public class C08 {
    public static void main(String[] args) {
//        int[] pre = {3, 9, 20, 15, 7};
//        int[] in = {9, 3, 15, 20, 7};
//        int[] pre = {1, 2};
//        int[] in = {2, 1};
        int[] pre = {3, 1, 2, 4};
        int[] in = {1, 2, 3, 4};
        printTree(buildTree(pre, in));
    }

    private static void printTree(TreeNode treeNode) {
        if(treeNode == null) {
            return;
        }
        System.out.println(treeNode.val);
        printTree(treeNode.left);
        printTree(treeNode.right);
    }

    // 不提交这个类
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    static HashMap<Integer, Integer> map = new HashMap<>();

    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null || preorder.length != inorder.length) {
            return null;
        }

        // 构建二叉树
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }

        return process(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    /*
        int[] pr = {3,9,20,15,7};
        int[] in = {9,3,15,20,7};
     */
    private static TreeNode process(int[] preorder, int l1, int r1, int[] inorder, int l2, int r2) {
        System.out.println(l1 + " " + r1 + " " + l2 + " " + r2);
        if(l1 > r1) {  // 可以带入  中序·2 1 先序 1 2的例子
            return null;
        }
        if (l1 == r1) {
            return new TreeNode(preorder[l1]);
        }
        TreeNode root = new TreeNode(preorder[l1]);
        Integer inIndex = map.get(preorder[l1]);

        root.left = process(preorder, l1 + 1, l1 + inIndex - l2, inorder, l2, inIndex - 1);
        root.right = process(preorder, l1 + inIndex - l2 + 1, r1, inorder, inIndex + 1, r2);

        return root;
    }
}
